\title{Technical Report: \\Online Robust Optimization with Kriging metamodel}
\author{Jun HU\footnote{OPS}}
\date{\today}

\documentclass[10pt]{article}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{graphicx} 
\usepackage{lmodern}

%\usepackage{pdfpages}


\renewcommand{\familydefault}{\sfdefault} %set default font Sans 
\renewcommand{\baselinestretch}{1.50}\normalsize %set line space 1.5

\providecommand{\expt}[1]{{\mathbb E}[ #1 ]}
\providecommand{\Besancon}[0]{Besan\c{c}on }
\providecommand{\term}[1]{\textbf{#1}}

\begin{document}

\maketitle

\begin{abstract}
This paper resumes the recent development in Robust Optimization. Several approaches will be essentially presented based on our particular case. A robust approach based on simulation-optimization will be proposed to deal with our specific case.
\\{\bf Keywords:} robust, non-convex,convex, stochastic optimization, online, recoverable, simulation-optimization, metamodel 
\end{abstract}

\tableofcontents


\pagebreak

\section{Introduction}
This paper concentrates itself in online robust optimization with the kriging metamodel, the SON network is a self-organizing system which can provide a tolerant solutions set in dynamic system. 



\subsection{Robust optimization}
Robust optimization tackles problems affected by uncertainty, providing solutions that are almost insensitive to perturbations in the model parameters \cite{Dellino2009thesis}. It can be roughly classified into two categories: 

\begin{itemize}
\item Offline robust optimization
\item Online robust optimization
\end{itemize}

by following the terminology of the online and offline optimization. The offline robust optimization concentrates in solving the problems whose uncertainties are pre-defined before the optimization. The problem scenarios are presented and known. Thus, the solutions obtained are insensitive on these pre-defined scenarios. For such class of problems, please refer the paper by Ben Tel and Nemirovski\cite{BenTel2002}. 


Recently Yu et al. \cite{Yu2010ROOT} developed an approach call ROOT (Robust Optimization Over Time) which considered the cost of solution modification with minor changing of situation. The objective is to find a sequence solutions $<S_1, \dots, S_k>$, where $1\leq k\leq l$, such that $k$ is minimal. Recoverable Robust Optimization\cite{Liebchen2007} may be consider as same approach. 


On the other hand, the online robust optimization is derived from online optimization, whose uncertainty is not pre-defined and not known before the optimization. Online robust optimization is a multi-step optimization process, it keeps the current time-slot optimized and also takes the future scenarios in account. The optimization process works on real time with the feedback (or rapid solution evaluation) or goes as offline with the estimated future scenarios at hand. 

\subsection{Online robust optimization algorithm}
Following the terminology of the online optimization problem, in online robust optimization problem, the uncertainties is unknown before the optimization process. The uncertainties in the future are estimated by the prediction procedure, which simulate the dynamic environment. 



MPC (Model Predictive Control)

The future scenarios prediction is an indispensable component in on-line algorithm scheme. The Figure~\ref{fig:online} illustrates the general scheme of an on-line algorithm. 

\begin{figure}[h]
\centering
\includegraphics[width=.6\textwidth]{pic/onlineScheme.pdf}
\caption{Online algorithm scheme}\label{fig:online}
\end{figure}

The future scenarios prediction makes the offline algorithms can be adapted in online optimization problems by introducing estimated unknown information as on-hand known information. 


\subsection{Simulation-optimization}
\term{Simulation-optimization} aims to identify the setting of the input parameters of a simulated system leading to optimal system performances. In practice, however, some of these parameters cannot be perfectly controlled due to measurement errors or other implementation issues, and because of the inherent uncertainty caused by fluctuations in the environment (e.g. temperature or pressure in physical and chemical processes or demand in inventory problems). Consequently, the classic optimal solution derived ignoring these sources of uncertainty may turn out to be sub-optimal or even infeasible. Robust optimization (RO) offers a way to tackle this class of problems, with the purpose of deriving solutions that are relatively insensitive to perturbations caused by the noise factors. A recent survey on robust optimization in simulation can be found in paper \cite{Beyer2007}. 


Due to the complexity of the models, the procedure of the simulation may be time consuming and costly. This paper presents the method to tackle robustness based on response surface methodology, specifically, the Kriging metamodels. This approach is basically adapting mean and variance as statistics to study the insensitivity of the response to possible variations in the noise factors. The consideration of Kriging as approximation is a reasoning that Kriging provides reliable approximation models of highly nonlinear functions \cite{Jin2003}. In Section \ref{sec:kriging}, the concept of the kriging model will be detailed. 



\section{ARIMA for forecasting}\label{sec:arima}
ARIMA (AutoRegressive Integrated Moving-Average) integrates the AR model and MA model with allowing differencing of the data series on non-stationary time series prediction. The general non-seasonal model of ARIMA is known as $ARIMA(p,d,q)$, where $p$ is the order of the autoregressive part, $d$ is the degree of first differencing involved and $q$ is the order of the moving average part. 


See the following regression equation (autoregression): 

\begin{equation}
Y_t = b_0 + b_1Y_{t-1} + b_2Y_{t-2} + \dots + b_pY_{t-p} + e_t
\end{equation}

where $Y_t$ is the forecast variable, $Y_{t-1},\dots,Y_{t-p}$ are the previous values of forecast variable $Y_t$ (explanatory variables), and $e_t$ is the white noise. The general non-seasonal model is known as ARIMA($p,d,q$), where $p$ is the order of the autoregressive part, $d$ is the degree of first differencing involved and $q$ is the order of the moving average part. 



\section{Kriging metamodel}\label{sec:kriging}
The metamodel is also called response surface, surrogate, emulators, etc. By definition, a metamodel is an explicit approximation of the implicit IO function (Input/Output) that is defined by the underlying simulation model. The underlying simulation can be either deterministic or stochastic (random). Deterministic models often represent the systems governed by the physical laws; while stochastic simulation models, including discrete-event simulation, often represent human being involved social systems. 

In a telecommunication network, there are existing both deterministic and stochastic simulation models. For instance, the simulation of the electromagnetic wave simulation respects the physics law, and the communication traffic among the mobile users is realized by the stochastic simulation model. In this paper, we restrict us exclusively dealing with the deterministic simulation by ignoring the discrete time events in network traffic. 


Here, we restrict us to focus on {\it Kriging} metamodel (also known as Gaussian Process Model inside the machine learning community). It can deal with both deterministic and stochastic simulation model. Kriging metamodel was originally developed by Daniel Krige, later on, it was applied to obtain a metamodel based on the experiments I/O data with deterministic simulation models. A recent survey of Kriging in simulation-based metamodeling can be found in \cite{Kleijnen2009}. The simpliest kriging metamodel is ordinary Kriging, it is suitable for the majority of the cases.  


\subsection{Ordinary kriging}
The Ordinary Kriging assumes that:

\begin{equation}
Y(x)= \mu(x) + \varepsilon(x)
\end{equation}\label{equ:kriging}

where $Y(x)$ is the metamodel representing the Input/Output function, $x\in \mathbb{R}^m$ is a design point in $m$-dimension space,  $\mu(x)$ is constant mean, $\varepsilon(x)$ is a stationary stochastic gaussian process with mean zero and variance $\sigma^2(x)$. The covariances of $Y(x+h)$ and $Y(x)$ exclusively depends on the distance (lag) $|h| = |(x+h)-x|$. 


The kriging predictor for non-simulated input point $x_0$ in $\mathbb{R}^m$ space, denoted $\hat{Y}(x_0)$, is a weighted ($\lambda_i, i\in n$) linear combination of all the $n$ simulated outputs (simulation experiments): 

\begin{equation}
\hat{Y}(x_0) = \sum^n_{i=1}\lambda_i\times Y(x_i)
\end{equation}

In the literature, usually, the bast linear unbiased estimator (BLUE) is applied to estimate the weights $\lambda_i$, it minimizes the mean squared prediction error:

\begin{equation}
MSE(\hat{Y}(x_0))=\expt{(Y(x_0)-\hat{Y}(x_0))^2}
\end{equation}

Above minimization must meet the condition that the predictor is unbiased: 

\begin{equation}
\expt{Y(x_0)} = \expt{\hat{Y}(x_0)}
\end{equation}

The optimal values for the kriging weights $\lambda_i$ depends on the correlations between the simulation outputs in the kriging model (Equ. \ref{equ:kriging}). The popular correlation function in kriging is Gaussian correlation function: 


\begin{equation}
corr[Y(x_i),Y(x_j)]=\prod^m_{k=1} exp(-\theta_k|x_{ik}-x_{jk}|^2)
\end{equation}

where $\theta_k$ denotes the important of input $k$ (the higher $\theta_k$ is, the less effect input $k$ has). The correlation function has inverse relation with the distance. In case of simulation, the type of the correlation function and the parameter values must be estimated. 


Based on \cite{KleijnenSurvey2013}
The parameters $(\mu, \sigma^2, \theta)$, where $\theta=(\theta_1,\dots,\theta_)$ are the hyper-parameters of kriging metamodel. The Kriging parameters are selected using the best linear unbiased predictor (BLUP) criterion which minimizes the mean squared error (MSE) of the predictor.


The interpolation property of Kriging is not desirable in random
simulation, because the observed average output per scenario is noisy. Therefore the Kriging metamodel may be changed such that it includes \term{intrinsic} noise. 


\subsection{Related works}



\section{Experiments of forecasting}
All the experiments are based on the network of \Besancon, the traffic data of network is obtained in Assert 7 on 4 June 2013. There are total cellulars in examined network. The hour by hour traffic data consists of 24 hours traffic density data for each cellular. 



\section{Experiments of Kriging}

\subsection{Experiment preparation}
We use again the \Besancon network as our benchmark. 


The experiments show the 

\subsection{Experimental results}



\section{Conclusion and perspectives}


\begin{itemize}
\item Initial network configuration based on static robust optimization 
\item Integration kriging in genetic algorithm
\end{itemize}

\bibliographystyle{abbrv}
\bibliography{robust}


\end{document}